Over time and with frequent use, databases often become disorganized. Accordingly, numerous attempts have been made to reorganize such databases. Reorganization of a database includes changing some aspect of the logical and/or physical arrangement of the database. Any database management system (DBMS) will require some type of reorganization. One type of reorganization involves restoration of clustering and removal of overflows. In particular, clustering relates to the storing of instances near each other if they meet certain criteria. One popular criterion is consecutive values of a key. Clustering is intended to reduce disk traffic for instances that a user often accesses in temporal proximity. However, a user's writing may fill data pages, decrease the amount of clustering, and degrade database performance. Accordingly, reorganization may restore performance.
Reorganization is a necessary feature in Database Management Systems (DBMSs). During most types of reorganization in a typical database, the area being reorganized is offline or only partially available.
However, with a highly available database (a database that is to be fully available 24 hours per day, 7 days per week), it is undesirable to have the database go offline for significant periods. Database applications that require high availability include reservations, finance (especially global finance), process control, hospitals, police, and armed forces. Even for less essential applications, many database administrators prefer 24-hour availability. Moreover, reorganization of a very large database may require a long offline period for reorganization, which is usually longer than the maximum tolerable offline period. With the increasing sizes of databases, which may contain several terabytes or even petabytes of data, a user will likely experience even a longer offline period. Based on the increasing sizes of databases, as well as, increasing demands by users to have 24 hour database access, the need for online reorganization will very likely increase.
The considerations discussed above call for the ability to reorganize the database online (e.g., concurrently with usage or incrementally within users' transactions), so that users can read and write the database during most or all phases of reorganization. The desire to have this capability is well known. As the amount of information and dependence on computers both increase, the number of very large or highly available databases will increase. Therefore, the importance of online reorganization will increase.
One strategy for online reorganization is called fuzzy reorganization, which involves reorganization by copying. This type of reorganization involves a reorganizer (the process that performs the reorganization) that records a current relative byte address (RBA) of a log. An RBA is a position in the log where a log entry can be written. At any time, the "current" RBA of the log is the position where the next log entry is written. An RBA is sometimes called a log sequence number (LSN). A log consists of a sequence of entries in a file (a region of storage), recording the changes that occur to a database. Then the reorganization copies data from an old (original) area for the table space to a new area for the table space, in reorganized form. Concurrently, users can use the DBMS's normal facilities to read and write the old area, and the DBMS uses its normal facilities to record the writing in a log. The reorganizer then reads the log and applies it to the new area to bring the new area up to date. Then, the reorganizer switches the users' accessing to the new area. In many DBMS's, however, each entry in the log identifies a record by the record's record identifier (RID). As an inherent part of reorganization the RIDs change. Therefore, when applying the log (which uses old RIDs) to the new area (which uses new RIDs), the problem of identification arises.
One way of overcoming this problem of identification is to have every record include a unique identifier that does not change during reorganization. However, it is often undesirable to have a restriction that each record must have a unique identifier that does not change during reorganization.
Another system describes garbage collection for persistent data by copying data and applying the log. See, for example, J. O'Toole et al., "Concurrent Compacting Garbage Collection of a Persistent Heap," Proc. 14th ACM Symp. operating Syst. Principles, December 1993 (Operating Syst. Review, SIGOPS, Vol. 27, No. 5), pp. 161-174. Each old record has a field that stores the address of the corresponding new record. Processing of the log uses this field to translate addresses in log entries. In a database context (which was not the context for this garbage collection) the technique of storing the address of the new record in the old record has serious disadvantages.
In particular, if a user deletes a record (and the DBMS generates a corresponding log entry) after the reorganizer has copied the record, then the reorganizer will eventually find the log entry, try to use the field to translate an address in the log entry from old to new, and apply the user's deletion in the new area. Between the user's deletion and the reorganizer's processing of the log entry, the DBMS might reuse the space that the deleted record occupied, so the new address may not be safely stored in the old (deleted) record. In addition, a data record is fairly large so the set of all data records can require many pages. Therefore, writing and reading the new addresses in the old data records can involve significant page input/output. Furthermore, storing the new record's address in the old record requires a shared lock while unloading the old record, an exclusive lock while reloading the new record (to write a new address in the old record), and a shared lock while processing the log (to translate the address). Therefore, this technique has a tendency to be slow and limits concurrency in the database. Furthermore, this technique may require extra space (which is permanent) in each data record for the address of the new record.
In contrast to fuzzy reorganization discussed above (which uses copying and a log), Reorganization can be performed in place (i.e., not by copying). One such strategy uses a table that maps RIDs to translate entries in the leaves of indexes. See, for example, E. Omiecinski et al., "Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering," IEEE Trans. Knowledge and Data Engin., Vol. 6, No. 2, April 1994, pp. 248-257. Reorganization in place does not use the log because use of the log is inappropriate here since there is only one copy of data. With this strategy for reorganization in place, each transaction by the user holds its locks until commitment of the transaction. However, this reduces the amount of concurrency in the database.
If each transaction by the user does not hold its locks until commitment of the transaction, reorganization in place is complex, especially if reorganization includes changing the assignment of records to pages, as in restoration of clustering. If a user scans a table space or index, and reorganization moves a record between the already-scanned area and the not-yet-scanned area, it must be assured that the user's scan processes the record exactly once, not twice or never. The feasibility of this approach has not yet been established. In addition, reorganization in place may cause more degradation of users' performance, since this type of reorganization writes (instead of reading) the area that users access.
Furthermore, reorganization may be accomplished by offline reorganization of fine-grained partitions. Specifically, a partition of a table space can be a unit of offline reorganization or other utilities, during usage or offline reorganization of other partitions. With a fine enough granularity of partitioning, offline reorganization of a partition may be fast enough to approximate 24 hour availability. However, making the granularity fine can slow the routing of users' accesses into the appropriate areas and increase the total space required for the partitions, storage descriptors. It also increases the probability that areas of growth and areas of shrinkage will be in different partitions. This increase in the probability increases the likely variation among the partitions' growth rates, thus increasing the total recommended amount of free space to reserve in the database. Also, offline reorganization (like some strategies for online reorganization) has a prerequisite period of quiescing of users' activities.
What is needed is a system that is capable of reorganizing a database online or incrementally with minimal offline periods. By eliminating or minimizing the amount of time offline, a user may retain the ability to read and/or write to the database during all or most phases of reorganization. In particular, what is needed is online reorganization for restoration of clustering and removal of overflows.
Moreover, what is needed is a system for online reorganization with the following properties. Records that do not require a unique identifier which does not change during reorganization. The ability for users to insert, update, and delete data during reorganization. Lack of need for a user transaction to hold its locks until commitment of a transaction. Reorganization that does not significantly degrade users' performance (e.g., by performing a large amount of locking). Reorganization that does not require permanent extra space in the area where users' data is stored. An internal processing by the reorganization that limits the amount of page input/output.
Applicants have identified the ability to reorganize databases using a combination of a log application with the use of a mapping table. No prior work exists that combines log application with the use of a mapping table.